---
categories: Number theory, Algorithms
---

A *number theoretic transform* is similar to a [fast Fourier transform](Fast Fourier transform), but instead of using complex [roots of unity](Root of unity), [roots of unity modulo $n$](Root of unity modulo n) are used. This allows computing convolutions where arithmetic is taken modulo $n$, and thus avoids using floating point numbers as is the case for fast Fourier transform.

## Problems
- [Counting tuples](https://projecteuler.net/problem=537)

## See also
- [Fast Fourier transform]()
- [Divide and conquer]()

## External links
- [Number theoretic transforms](http://www.apfloat.org/ntt.html)
- [A week that ends with FFT](http://petr-mitrichev.blogspot.com/2014/06/this-week-in-competitive-programming_11.html)
- [Fast convolution for 64-bit integers](http://codeforces.com/blog/entry/45298)